{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Solving Questions With Brainpower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解决智力问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>questions</code>&nbsp;，其中&nbsp;<code>questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>这个数组表示一场考试里的一系列题目，你需要 <strong>按顺序</strong>&nbsp;（也就是从问题 <code>0</code><strong>&nbsp;</strong>开始依次解决），针对每个问题选择 <strong>解决</strong>&nbsp;或者 <strong>跳过</strong>&nbsp;操作。解决问题 <code>i</code>&nbsp;将让你 <b>获得</b>&nbsp;&nbsp;<code>points<sub>i</sub></code>&nbsp;的分数，但是你将 <strong>无法</strong>&nbsp;解决接下来的&nbsp;<code>brainpower<sub>i</sub></code>&nbsp;个问题（即只能跳过接下来的 <code>brainpower<sub>i</sub></code><sub>&nbsp;</sub>个问题）。如果你跳过问题&nbsp;<code>i</code>&nbsp;，你可以对下一个问题决定使用哪种操作。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，给你&nbsp;<code>questions = [[3, 2], [4, 3], [4, 4], [2, 5]]</code>&nbsp;：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>如果问题&nbsp;<code>0</code>&nbsp;被解决了， 那么你可以获得&nbsp;<code>3</code>&nbsp;分，但你不能解决问题&nbsp;<code>1</code> 和&nbsp;<code>2</code>&nbsp;。</li>\n",
    "\t\t<li>如果你跳过问题&nbsp;<code>0</code>&nbsp;，且解决问题&nbsp;<code>1</code>&nbsp;，你将获得 <code>4</code> 分但是不能解决问题&nbsp;<code>2</code> 和&nbsp;<code>3</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回这场考试里你能获得的 <strong>最高</strong>&nbsp;分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>questions = [[3,2],[4,3],[4,4],[2,5]]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>解决问题 0 和 3 得到最高分。\n",
    "- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。\n",
    "- 不能解决问题 1 和 2\n",
    "- 解决问题 3 ：获得 2 分\n",
    "总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>解决问题 1 和 4 得到最高分。\n",
    "- 跳过问题 0\n",
    "- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。\n",
    "- 不能解决问题 2 和 3\n",
    "- 解决问题 4 ：获得 5 分\n",
    "总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= questions.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>questions[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= points<sub>i</sub>, brainpower<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [solving-questions-with-brainpower](https://leetcode.cn/problems/solving-questions-with-brainpower/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [solving-questions-with-brainpower](https://leetcode.cn/problems/solving-questions-with-brainpower/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,2],[4,3],[4,4],[2,5]]', '[[1,1],[2,2],[3,3],[4,4],[5,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        sz = len(questions)\n",
    "        @cache\n",
    "        def f1(start):\n",
    "            if start >= sz:\n",
    "                return 0\n",
    "            points, brainpower = questions[start]\n",
    "            a = points + f1(start + brainpower + 1)\n",
    "            b = f1(start + 1)\n",
    "            return max(a, b)\n",
    "        return f1(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        if n == 1:\n",
    "            return questions[0][0]\n",
    "        questions[-1] = questions[-1][0]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if i + questions[i][1] + 1 >= n:\n",
    "                questions[i] = max(questions[i + 1], questions[i][0])\n",
    "            else:\n",
    "                questions[i] = max(questions[i + 1], questions[i][0] + questions[i+questions[i][1]+1])\n",
    "        return questions[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 贪心算法，也算动态规划，本次回答问题 + [next:last]这个区间的总和\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        length = len(questions)\n",
    "        idx = length-1\n",
    "        ans = 0\n",
    "        while idx>=0:\n",
    "            # 选择本次回答问题的情况\n",
    "            # 分数\n",
    "            point = questions[idx][0]\n",
    "            # 下一个能获取获取的答案的位置。\n",
    "            add_idx = questions[idx][1] + 1\n",
    "            # 优化点，这里有一个点在于next_idx比较随机，导致空间局部性原理不好。\n",
    "\n",
    "            # 假设从idx + add_idx = next_idx 的最佳答案已经存在 questions[next_idx][0]\n",
    "            # 那么做这道题得到的分数： questions[next_idx][0] + point\n",
    "            max_sum =0 if idx+add_idx>=length else questions[idx+add_idx][0]\n",
    "\n",
    "            # 不做这道题比较，我们做下一道题。\n",
    "            next_sum = questions[idx+1][0] if idx < length-1 else 0\n",
    "\n",
    "            # 做这道题和不做这道题，哪个分数更高\n",
    "            questions[idx][0] = max(next_sum,max_sum+point)\n",
    "\n",
    "            # 存放的答案和之前的ans比较\n",
    "            idx = idx - 1\n",
    "\n",
    "        \n",
    "        return questions[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            p, b = questions[i - 1]\n",
    "            dp[i] = max(dp[i], dp[i - 1])\n",
    "            t = min(i + b, n)\n",
    "            dp[t] = max(dp[t], dp[i - 1] + p)\n",
    "        return dp[n]\n",
    "\n",
    "        # n = len(questions)\n",
    "        # f = [0] * (n + 1)\n",
    "        # for i, (point, brainpower) in enumerate(questions):\n",
    "        #     f[i + 1] = max(f[i + 1], f[i])\n",
    "        #     j = min(i + brainpower + 1, n)\n",
    "        #     f[j] = max(f[j], f[i] + point)\n",
    "        # return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: list[list[int]]) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        h = list()\n",
    "        for i, (p, b) in enumerate(questions):\n",
    "            while h and h[0][0] < i:\n",
    "                cur = max(cur, heappop(h)[1])\n",
    "            if cur + p > ans:\n",
    "                ans = cur + p\n",
    "            heappush(h, (i + b, cur + p))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "Event = namedtuple(\"Event\", \"time score\")\n",
    "class Solution:\n",
    "    def mostPoints(self, A: List[List[int]]) -> int:\n",
    "        n = len(A)\n",
    "        # store Events, sorted by time asc, \n",
    "        # store Events, sorted by score, asc\n",
    "        tpq = SortedList(key=lambda e:e.time)\n",
    "        spq = SortedList(key=lambda e:e.score)\n",
    "        cs = 0\n",
    "        for i, (pts, brainpower) in enumerate(A):\n",
    "            while tpq and tpq[0].time==i:\n",
    "                event = tpq.pop(0)\n",
    "                cs = max(cs, event.score)\n",
    "                spq.remove(event)\n",
    "\n",
    "            event = Event(i+brainpower+1,cs+pts)\n",
    "            tpq.add(event)\n",
    "            spq.add(event)\n",
    "        \n",
    "        return spq[-1].score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        # dp[i]: 从questions[i]开始答题\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            j = min(i + questions[i][1] + 1, n)\n",
    "            dp[i] = max(dp[i + 1], dp[j] + questions[i][0])\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        dp = [0] * (n + 1)   # 解决每道题及以后题目的最高分数\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            dp[i] = max(dp[i + 1], questions[i][0] + dp[min(n, i + questions[i][1] + 1)])\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def mostPoints(self, questions):\n",
    "        n = len(questions)\n",
    "        score = [0 for _ in range(n+1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            score[i] = max(score[i + 1], score[min(n, i + 1 + questions[i][1])] + questions[i][0])\n",
    "        return score[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in range(2)] for _ in range(len(questions))]\n",
    "        # 最后一位，取不取的，对其他数字都没有影响了，取了有分，不取0\n",
    "        dp[-1][0] = 0\n",
    "        dp[-1][1] = questions[-1][0]\n",
    "        # 这个需要倒过来看，否则会很麻烦\n",
    "        for i in range(len(questions)-2, -1, -1):\n",
    "            # 这个数如果不取，那就取它后面那个值的最大值\n",
    "            dp[i][0] = max(dp[i+1][0], dp[i+1][1])\n",
    "            # 这个数如果要取，那么只能加上往后数q[i][1]+1位置的max值\n",
    "            # 如果这个q[i][1] 要大于 len(q)-i，说明后面所有的数它都盖住了\n",
    "\n",
    "            ni = questions[i][1]+i+1\n",
    "            if ni >= len(questions):\n",
    "                k1 = questions[i][0]\n",
    "            else:\n",
    "                k1 = questions[i][0] + max(dp[ni][0], dp[ni][1])\n",
    "            dp[i][1] = k1\n",
    "            # print(i, dp)\n",
    "        return max(dp[0][0], dp[0][1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def mostPoints(self, questions) -> int:\r\n",
    "        l = []\r\n",
    "        heapq.heapify(l)\r\n",
    "        dp = [[0]*2 for _ in range(len(questions))]\r\n",
    "        dp[0][1] = questions[0][0]\r\n",
    "        heapq.heappush(l, (questions[0][1], dp[0][1]))\r\n",
    "        mx = 0\r\n",
    "        for i in range(1, len(questions)):\r\n",
    "            while l and l[0][0] < i:\r\n",
    "                end, point = heapq.heappop(l)\r\n",
    "                mx = max(point, mx)\r\n",
    "\r\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1])\r\n",
    "            dp[i][1] = mx + questions[i][0]\r\n",
    "            heapq.heappush(l, (questions[i][1]+i, dp[i][1]))\r\n",
    "        return max(dp[-1])\r\n",
    "\r\n",
    "\r\n",
    "print(Solution().mostPoints([[3,2], [4,3], [4,4], [2,5]]))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions):\n",
    "            n = len(questions)\n",
    "            dp = defaultdict(int)\n",
    "            \n",
    "            for i in range(n-1,-1,-1):\n",
    "                point, skip = questions[i]\n",
    "                dp[i] = max(dp[i+1], dp[i+1+skip]+point)\n",
    "            return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        jump_from = defaultdict(list)\n",
    "        for start, (point, brain_power) in enumerate(questions):\n",
    "            dest = start+brain_power+1\n",
    "            if dest < len(questions):\n",
    "                jump_from[dest].append(start)\n",
    "        \n",
    "        dp = [[0,0] for _ in questions]\n",
    "        dp[0][1] = questions[0]\n",
    "        ret = questions[0][0]\n",
    "        for i in range(len(questions)):\n",
    "            cur = dp[i-1][0]\n",
    "            for pre in jump_from[i]:\n",
    "                cur = max(cur, dp[pre][1])\n",
    "            dp[i][0] = cur\n",
    "            dp[i][1] = cur + questions[i][0]\n",
    "            ret = max(ret, dp[i][1])\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n=len(questions)\n",
    "        dp=[0]*n #计算每个格式的dp，注意，不含当前得分\n",
    "        air=[0]*n #保存仍未落地的跳跃（为终点计算准备）\n",
    "        d=collections.defaultdict(list) #把每个跳跃的起点，作为数组保存在落点\n",
    "        for i,a in enumerate(questions):\n",
    "            x,y=a\n",
    "            if i>0:\n",
    "                a=[dp[i-1]] #找最大值 1、从[i-1]跳过来，直接继承 dp[i-1]\n",
    "                for dk in d[i]: #2、跳跃过来的，都有记录\n",
    "                    a.append(dp[dk]+questions[dk][0])\n",
    "                    air[dk]=0 #消除起跳（为终点计算准备）\n",
    "                dp[i]=max(a)\n",
    "            d[i+y+1].append(i)\n",
    "            air[i]=1 #开始起跳（为终点计算准备）\n",
    "        ans=[dp[n-1]+questions[n-1][0]] #走过终点的得分\n",
    "        for airk,x in enumerate(air):\n",
    "            if x==1:\n",
    "                ans.append(dp[airk]+questions[airk][0]) #跳跃过终点的得分\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n=len(questions)\n",
    "        dp=[0]*n\n",
    "        air={}\n",
    "        d=collections.defaultdict(list)\n",
    "        for i,a in enumerate(questions):\n",
    "            ##print(\"a=\",a)\n",
    "            x,y=a\n",
    "            if i>0:\n",
    "                #找最大值\n",
    "                #1、从上一个跳过来，直接继承 dp[i-1]\n",
    "                #2、从其他得分休息过来，到数据中找\n",
    "                a=[dp[i-1]]\n",
    "                for dk in d[i]:\n",
    "                    a.append(dp[dk]+questions[dk][0])\n",
    "                    del air[dk]\n",
    "                    #print(i,\" end air. onair:\",air)\n",
    "                dp[i]=max(a)\n",
    "                #print(\"a:\",a)\n",
    "            #print(\"i,dp[i] \",i,dp[i])\n",
    "            #if i+y+1<n:\n",
    "            d[i+y+1].append(i)\n",
    "            air[i]=1 #空投\n",
    "            ##print(i,\" start air ...\")\n",
    "            #print(\"d:\",d)\n",
    "        ans=[dp[n-1]+questions[n-1][0]]\n",
    "        ##print(\"ans:\",dp[n-1],questions[n-1][0])\n",
    "        ##print(\"still onair:\",air)\n",
    "        for airk in air.keys():\n",
    "            ans.append(dp[airk]+questions[airk][0])\n",
    "            #print(\"ans:\",dp[airk],questions[airk][0])\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        dp=[0] *(n+10000000)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i] = max(dp[i+1],dp[i+questions[i][1]+1]+questions[i][0])\n",
    "        print(dp[:n])\n",
    "        return dp[0] \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, q: List[List[int]]) -> int:\n",
    "        q0=len(q)\n",
    "        dp=[0]*(q0+10000000)\n",
    "        for i in range(q0-1,-1,-1):\n",
    "            dp[i]=max(dp[i+1],dp[i+q[i][1]+1]+q[i][0])\n",
    "        return (dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    questions_temp = []\n",
    "    length = 0\n",
    "    remain = []\n",
    "\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        self.questions_temp = questions\n",
    "        self.length = len(questions)\n",
    "        self.remain = [0] * self.length\n",
    "        return self.f(0)\n",
    "\n",
    "    def f(self, index: int) -> int:\n",
    "        if self.remain[index] != 0:\n",
    "            return self.remain[index]\n",
    "        elif (index + 1 >= self.length):\n",
    "            self.remain[index] = self.questions_temp[index][0]\n",
    "        elif (index + self.questions_temp[index][1] + 1 >= self.length):\n",
    "            self.remain[index] = max(self.questions_temp[index][0], self.f(index + 1))\n",
    "        else :\n",
    "            self.remain[index] = max(self.questions_temp[index][0] + self.f(index + self.questions_temp[index][1] + 1), self.f(index + 1))\n",
    "        return self.remain[index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        # print(len(questions))\n",
    "        self.vs = [0]*len(questions)\n",
    "        return self.bs(questions,0,len(questions),0)\n",
    "\n",
    "    def bs(self, questions: List[List[int]], i:int,count:int,total:int) -> int:\n",
    "        if(i>=count):\n",
    "            return total\n",
    "        if(self.vs[i]>0):\n",
    "            return total+self.vs[i]\n",
    "        \n",
    "        t1 = self.bs(questions,i+1+questions[i][1],count,questions[i][0])\n",
    "        t2 = self.bs(questions,i+1,count,0)\n",
    "        m = max(t1,t2)\n",
    "        self.vs[i]=m\n",
    "        return total+m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self, idx: int) -> int:\n",
    "        if idx not in self.mp:\n",
    "            if idx >= len(self.questions): return 0\n",
    "            self.mp[idx] = max(self.dp(idx + 1), self.questions[idx][0] + self.dp(idx + self.questions[idx][1] + 1))\n",
    "        return self.mp[idx]\n",
    "\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        self.questions = questions\n",
    "        self.mp = DefaultDict(int)\n",
    "        return self.dp(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        self.questions = questions\n",
    "        self.cache = dict()\n",
    "        return self.mostPointsRecursive(0)\n",
    "        \n",
    "    def mostPointsRecursive(self, i):\n",
    "        if i >= len(self.questions):\n",
    "            return 0\n",
    "        if i in self.cache:\n",
    "            return self.cache[i]\n",
    "        points, brainpower = self.questions[i]\n",
    "        result = max(points + self.mostPointsRecursive(i+brainpower+1), self.mostPointsRecursive(i+1))\n",
    "        self.cache[i] = result\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions):\n",
    "        l = len(questions)\n",
    "        ss = [-1] * l\n",
    "        def s(i):\n",
    "            if i >= l:\n",
    "                return 0\n",
    "            if ss[i] != -1:\n",
    "                return ss[i]\n",
    "            ss[i] = max(questions[i][0] + s(questions[i][1] + i + 1), s(i + 1))\n",
    "            return ss[i]\n",
    "        return s(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions):\n",
    "        l = len(questions)\n",
    "        ss = [-1] * l\n",
    "        def s(i):\n",
    "            if i >= l:\n",
    "                return 0\n",
    "            if ss[i] != -1:\n",
    "                return ss[i]\n",
    "            ss[i] = max(questions[i][0] + s(questions[i][1] + i + 1), s(i + 1))\n",
    "            return ss[i]\n",
    "        return s(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(i, cache, questions):\n",
    "            if i >= len(questions):\n",
    "                return 0\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "\n",
    "            a = dfs(i + 1, cache, questions)\n",
    "            b = questions[i][0] + dfs(i + questions[i][1] + 1, cache, questions)\n",
    "            cache[i] = max(a, b)\n",
    "            return cache[i]\n",
    "\n",
    "        return dfs(0, cache, questions)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        memo = {}\n",
    "        def dp(i):\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            \n",
    "            res = max(dp(i+1), questions[i][0] + dp(i + questions[i][1]+1))\n",
    "            memo[i] = res\n",
    "            return res\n",
    "        dp(0)\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        d=dict()\n",
    "        def f(pos):\n",
    "            if pos in d:return d[pos]\n",
    "            if pos<len(questions):\n",
    "                r1=questions[pos][0]+f(pos+questions[pos][1]+1)\n",
    "                r2=f(pos+1)\n",
    "                d[pos]=max(r1,r2)\n",
    "                return d[pos]\n",
    "            else:\n",
    "                return 0\n",
    "        v=f(0)\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        # 得分 然后跳转 或者直接跳到下一个\n",
    "\n",
    "        def getPoints(questions, location, record):\n",
    "            if location >= len(questions):\n",
    "                return 0\n",
    "\n",
    "            if location in record:\n",
    "                return record[location]\n",
    "\n",
    "            score = questions[location][0]\n",
    "            step = questions[location][1]\n",
    "\n",
    "            record[location] = max(score+getPoints(questions, location+step+1, record), getPoints(questions, location+1, record))\n",
    "            return record[location]\n",
    "\n",
    "        return getPoints(questions, 0, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, qus: List[List[int]]) -> int:\n",
    "        n = len(qus)\n",
    "        dp = [-1] * n\n",
    "#         pr = [-1] * n\n",
    "#         for idx in range(n):\n",
    "#             nx = idx + qus[idx][1] + 1\n",
    "#             if nx < n:\n",
    "#                 pr[nx] = idx\n",
    "        \n",
    "#         print(pr)\n",
    "#         print(\"####\")\n",
    "#         for i in range(n):\n",
    "#             preIdx = pr[i]\n",
    "#             point = p = qus[i][0]\n",
    "#             if preIdx != -1:\n",
    "#                 dp[i] = max(dp[preIdx] + point, dp[i])\n",
    "#                 dp[i] = max(dp[preIdx+1], dp[i])\n",
    "#             else:\n",
    "#                 dp[i] = point\n",
    "#             print(dp)\n",
    "            \n",
    "            \n",
    "            \n",
    "        def dfs(idx):\n",
    "            if idx >= len(qus):\n",
    "                return 0\n",
    "            if dp[idx] != -1:\n",
    "                return dp[idx]\n",
    "            p = qus[idx][0]\n",
    "            nx = idx + qus[idx][1] + 1\n",
    "            dp[idx] = max(p + dfs(nx), dfs(idx+1))\n",
    "            \n",
    "            return dp[idx]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "            \n",
    "        return max(dp)\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        cache = {}\n",
    "        def dfs(i):\n",
    "            if i >= len(questions):\n",
    "                return 0\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "            p, b = questions[i]\n",
    "            res1 = p + dfs(i+b+1)\n",
    "            res2 = dfs(i+1)\n",
    "            #print(i, res1, res2, mask)\n",
    "            cache[i] = max(res1, res2)\n",
    "            return max(res1, res2)\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, q: List[List[int]]) -> int:\n",
    "        q0=len(q)\n",
    "        def dfs(x):\n",
    "            if x in map1:\n",
    "                return map1[x]\n",
    "            if x>=q0:\n",
    "                return 0\n",
    "            ans=max(dfs(x+1),dfs(x+q[x][1]+1)+q[x][0])\n",
    "            map1[x]=ans\n",
    "            return ans\n",
    "        map1={}\n",
    "        return (dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        record = {}\n",
    "        def dfs(i=0):\n",
    "            count = 0\n",
    "            if i<n:\n",
    "                if i in record:\n",
    "                    return record[i]\n",
    "                no_choice = dfs(i+1)+count\n",
    "                points,passed = questions[i]\n",
    "                choice = points + dfs(passed+i+1)+count\n",
    "                res= max(choice,no_choice)\n",
    "                record[i]=res \n",
    "                return res\n",
    "            else:\n",
    "                return count\n",
    "\n",
    "        return dfs()\n",
    "        \n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, q: List[List[int]]) -> int:\n",
    "        # n = len(q)\n",
    "        # dp = collections.defaultdict(int)\n",
    "        # def dfs(i,score):\n",
    "        #     if i >= n:\n",
    "        #         dp[(i,score)] = score\n",
    "        #         return dp[(i,score)]\n",
    "        #     dp[(i,score)] = max(dfs(i+1,score),dfs(i + q[i][1] + 1,score+q[i][0]))\n",
    "        #     return dp[(i,score)]\n",
    "        # return dfs(0,0)\n",
    "        n = len(q)\n",
    "        dp = collections.defaultdict(int)\n",
    "        def dfs(i):\n",
    "            if dp[i]!= 0:\n",
    "                return dp[i]\n",
    "            if i >= n:\n",
    "                dp[i] = 0\n",
    "                return dp[i]\n",
    "            dp[i] = max(dfs(i+1),dfs(i+q[i][1]+1) + q[i][0])\n",
    "            return dp[i]\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        # @functools.lru_cache(None)\n",
    "        store = defaultdict(int)\n",
    "        \n",
    "        def solve(start = 0):\n",
    "            if start >= len(questions):\n",
    "                return 0\n",
    "            point, brain = questions[start]\n",
    "            if start + brain + 1 not in store:\n",
    "                store[start + brain + 1] = solve(start + brain + 1)\n",
    "            if start + 1 not in store:\n",
    "                store[start + 1] = solve(start + 1)\n",
    "            return max(point + store[start + brain + 1], store[start + 1])\n",
    "        \n",
    "        return solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(index):\n",
    "            v=dp(index+1) if index+1<len(questions) else 0\n",
    "            if index+questions[index][1]+1<len(questions): v=max(v,questions[index][0]+dp(index+questions[index][1]+1))\n",
    "            else: v=max(v,questions[index][0])\n",
    "            return v\n",
    "\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(index):\n",
    "            v=dp(index+1) if index+1<len(questions) else 0\n",
    "            if index+questions[index][1]+1<len(questions): v=max(v,questions[index][0]+dp(index+questions[index][1]+1))\n",
    "            else: v=max(v,questions[index][0])\n",
    "            return v\n",
    "\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        # @lru_cache(maxsize=None)\n",
    "        # def dp(i):\n",
    "        #     if questions[i][1] + i + 1 >= len(questions):\n",
    "        #         return questions[i][0]\n",
    "        #     return questions[i][0] + max([dp(j) for j in range(questions[i][1]+i+1, len(questions))])\n",
    "        \n",
    "        # return max(dp(i) for i in range(len(questions)))\n",
    "        # 子问题图有n个顶点， 每个顶点有len(questions)-questions[i][1]-1条边\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dp(i):\n",
    "            if i >= len(questions):\n",
    "                return 0\n",
    "            return max(dp(i+1), questions[i][0] + dp(questions[i][1]+i+1))\n",
    "        return dp(0)\n",
    "\n",
    "        # dp = [0]*(len(questions)+1)\n",
    "        # for i in range(len(questions)-1, -1, -1):\n",
    "        #     dp[i] = max(dp[i+1], questions[i][0]+dp[min(len(questions), questions[i][1]+i+1)])\n",
    "        # return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n=len(questions)\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x>n-1:\n",
    "                return 0\n",
    "            res=max(dfs(x+1),dfs(x+questions[x][1]+1)+questions[x][0])\n",
    "            return res\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n=len(questions)\n",
    "        # #关键点事倒序\n",
    "        # dp=[0]*(n+1)\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     index=questions[i][1]+1+i\n",
    "        #     if index<n:\n",
    "        #         dp[i]=max(dp[i+1],questions[i][0]+dp[index])\n",
    "        #     else:\n",
    "        #         dp[i]=max(questions[i][0],dp[i+1])\n",
    "        # return dp[0]\n",
    "        #记忆化搜索\n",
    "        questions = questions[::-1]\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            return max(dfs(i-1),dfs(i-questions[i][1]-1)+questions[i][0])\n",
    "        return dfs(n-1)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n: return 0\n",
    "            ans = dfs(i + 1)\n",
    "            score, boundary = questions[i]\n",
    "            ans = max(ans, dfs(i + boundary + 1) + score)\n",
    "            return ans\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostPoints(self, questions: List[List[int]]) -> int:\n",
    "        n = len(questions)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            return max(dfs(i+1 + questions[i][1]) + questions[i][0], dfs(i+1))\n",
    "        return dfs(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
